package Sort;

/**
 * 时间复杂度:
 *      最坏:O(n ^ 2)
 *      最好:O(n)
 * 空间复杂度:
 *      O(1)
 * 稳定性:
 *      稳定
 * 适用:
 *      待排序序列趋于有序
 */
public class InsertSort {
    public void Sort(int[] array)
    {
        for(int i = 1; i < array.length; i++)
        {
            int tmp = array[i];
            int j = i - 1;
            for(; j >= 0; j--)
            {
                if(array[j] > tmp)
                {
                    array[j + 1] = array[j];
                }
                else
                {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
}
